GATE IT 2007
Q31.
Consider the sequence \left \langle x_n \right \rangle,\; n \geq 0 defined by the recurrence relation x_{n + 1} = c \cdot (x_n)^2 - 2, where c > 0. For which of the following values of c, does there exist a non-empty open interval (a, b) such that the sequence x_n converges for all x_0 satisfying a < x_0 < b? i. 0.25 ii. 0.35 iii. 0.45 iv. 0.5Q33.
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty(Q) returns true if the queue is empty, false otherwise. ii. delete(Q) deletes the element at the front of the queue and returns its value. iii. insert(Q,i) inserts the integer i at the rear of the queue. Consider the following function void f (queue Q) { int i ; if (!isEmpty(Q)) { i = delete(Q); f(Q); insert(Q, i); } } What operation is performed by the above function f ?Q34.
Consider the following relation schemas : b-Schema = (b-name, b-city, assets) a-Schema = (a-num, b-name, bal) d-Schema = (c-name, a-number) Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation. Consider the following query: \Pi _{c-name}(\sigma _{b-city="Agra" \wedge bal \lt 0} (branch \Join (account \Join depositor))) Which one of the following queries is the most efficient version of the above query ?Q35.
Consider a selection of the form \sigma_{A\leq 100} (r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?Q36.
Consider the regular expression R = (a + b)^* (aa + bb) (a + b)^* Which deterministic finite automaton accepts the language represented by the regular expression R?Q37.
A hard disk system has the following parameters : Number of tracks = 500 Number of sectors/track = 100 Number of bytes /sector = 500 Time taken by the head to move from one track to adjacent track = 1 ms Rotation speed = 600 rpm. What is the average time taken for transferring 250 bytes from the disk ?Q38.
Consider the regular expression R = (a + b)^* \ (aa + bb) \ (a + b)^* Which one of the regular expressions given below defines the same language as defined by the regular expression R ?Q39.
Consider the regular expression R = (a + b)^* (aa + bb) (a + b)^* Which of the following non-deterministic finite automata recognizes the language defined by the regular expression R? Edges labeled \lambda denote transitions on the empty string.Q40.
A partial order P is defined on the set of natural numbers as follows. Here \frac{x}{y} denotes integer division. i.(0, 0) \in P. ii.(a, b) \in P if and only if (a \% 10) \leq (b \% 10) and (\frac{a}{10},\frac{b}{10})\in P. Consider the following ordered pairs: i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153) Which of these ordered pairs of natural numbers are contained in P?